package com.linwen.excise.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : linwen
 * @date : 5:48 下午 2020/11/1
 */
public class _22括号生成 {
    private static List<String> result;
    public static void main(String[] args) {
        int n = 3;
        System.out.println(generateParenthesis(n));
    }

    private static List<String> generateParenthesis(int n) {
        result = new ArrayList<String>();
        _generate2(0,0,n,"");
        return result;
    }

    /**
     * 对括号合法性进行检查
     * @param left
     * @param right
     * @param n
     * @param s
     */
    private static void _generate2(int left, int right, int n, String s) {
        if(left==n&&right==n){
            result.add(s);
            return;
        }
        //能添加左括号
        if(left<=n){
            _generate2(left+1,right,n,s+"(");
        }
        //能添加右括号
        if(right<left){
            _generate2(left,right+1,n,s+")");
        }
    }
}
